package cn.xiaolang.function.data_structure;

/**
 * 整数除法(两数相除)
 * <p>
 * 给定两个整数a和b ，求它们的除法的商: a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。
 * 注意：
 * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
 * 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231−1]。本题中，如果除法结果溢出，则返回 231 − 1
 * <p>
 * 示例 1：
 * 输入：a = 15, b = 2
 * 输出：7
 * 解释：15/2 = truncate(7.5) = 7
 * <p>
 * 示例 2：
 * 输入：a = 7, b = -3
 * 输出：-2
 * 解释：7/-3 = truncate(-2.33333..) = -2
 * <p>
 * 示例 3：
 * 输入：a = 0, b = 1
 * 输出：0
 * <p>
 * 示例 4：
 * 输入：a = 1, b = 1
 * 输出：1
 * <p>
 * 提示:
 * <p>
 * -231 <= a, b <= 231 - 1
 * b != 0
 */
public class No10divide {

    public static void main(String[] args) {
        System.out.println(divide(-2147483648, 1262480350));
        System.out.println(divide(-1, -1));
        System.out.println(divide(15, 2));
        System.out.println(divide(7, -3));
        System.out.println(divide(-1, 1));
    }

    public static int divide(int a, int b) {
        int result = 0;
        boolean isNegative = (a < 0 && b > 0) || (a > 0 && b < 0);
        // 边界值处理，除数最小值
        if (a == Integer.MIN_VALUE) {
            if (Math.abs(b) == 1) {
                return b < 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            a = (b < 0) ? a - b : a + b;
            result++;
        }
        // 边界值处理，被除数最小值 || 被除数大于除数等
        if (b == Integer.MIN_VALUE || Math.abs(a) < Math.abs(b) || a == 0) {
            return isNegative ? -result : result;
        }
        // 转换成正数处理
        a = (a < 0) ? -a : a;
        b = (b < 0) ? -b : b;
        if (a == b) {
            return isNegative ? -1 : 1;
        }
        /*
         * 除法转减法
         * 1. 15/2 = 20 - 2 - 2 - 2 - ...得7余1
         * 2. 7/-3 = 7 - 3 - 3  得-2余-1
         */
        int mid = a;
        while (mid >= b) {
            mid = mid - b;
            result++;
        }
        return isNegative ? -result : result;

    }
}
